package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.ArrayDeque;

/**
 * @author: xiaomi
 * @date: 2021/3/28
 * @description: 173. 二叉搜索树迭代器
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 * boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
 * int next()将指针向右移动，然后返回指针处的数字。
 */
public class B_173_二叉搜索树迭代器 {


    public static void main(String[] args) {
        test1();
    }

    static void test1() {
        BSTIterator action = new BSTIterator(TreeNode.stringToTreeNode("[7, 3, 15, null, null, 9, 20]"));
        System.out.println(action.next());
        System.out.println(action.next());
        System.out.println(action.hasNext());
        System.out.println(action.next());

        System.out.println(action.hasNext());
        System.out.println(action.next());
        System.out.println(action.hasNext());
        System.out.println(action.next());
        System.out.println(action.hasNext());
    }

    /**
     * 1.constructor 中使用 O(h) 的栈来保存一路向左遍历的节点
     */
    static class BSTIterator {


        ArrayDeque<TreeNode> stack = new ArrayDeque<>();

        TreeNode curNode = null;

        public BSTIterator(TreeNode root) {
            if (root == null) {
                return;
            }
            curNode = root;
            while (curNode != null) {
                stack.addLast(curNode);
                curNode = curNode.left;
            }
            //此时 curNode == null
            //建立一个哨兵节点
            TreeNode guard = new TreeNode();
            stack.peekLast().left = guard;

            curNode = guard;
        }

        /**
         * 由于保证 next 有，所以不需要考虑
         * 将当前指针指向下一个节点
         *
         * @return
         */
        public int next() {
            if (curNode.right != null) {
                TreeNode prevNode = curNode.right;
                curNode = prevNode.left;
                while (curNode != null) {
                    stack.addLast(prevNode);
                    prevNode = curNode;
                    curNode = curNode.left;
                }
                curNode = prevNode;
            } else {
                curNode = stack.removeLast();
            }
            return curNode.val;
        }

        public boolean hasNext() {
            if (curNode == null) {
                return false;
            }

            if (curNode.right == null && stack.isEmpty()) {
                return false;
            }
            return true;
        }

    }
}

